COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnify{1100}
C00014 ENDMK
C⊗;
\magnify{1100}
\chcode`|=13
\def|#1|{\hbox{\it#1\/}}
\parindent 0pt
\parskip 0pt
\def\pskip{\penalty-1000\vskip 6pt plus 2pt minus 1pt}
\def\ppskip{\penalty-2000\vskip 10pt plus 3pt minus 2pt}
\def\no(#1){\noindent\hbox to 6em{(#1)\hfill}}
\chcode`⊗=13
\def⊗{\hbox to 2em{}}
\def\IF{\mathop{\bf if}}
\def\THEN{\mathrel{\bf then}}
\def\ELSE{\mathrel{\bf else}}
\def\AND{\mathrel{\bf and}}
\def\OR{\mathrel{\bf or}}
\def\NOT{\mathop{\bf not}}
\def\N{\mathop{\bf n}}
\def\T{\hbox{\tt T}}
\def\NIL{\hbox{\tt NIL}}
\def\.{\mathbin{.}}
\def\A{\mathop{\bf a}}
\def\D{\mathop{\bf d}}
\def\EQ{\mathrel{\bf eq}}
\def\AT{\mathop{\bf at}}
\def\quote#1{\hbox{\sfcode`.=1000\tt#1}}
\def\list#1{\langle#1\rangle}

\ctrline{CS 206---Recursive Programming and Proving}
\ctrline{Homework 1 Solutions}
\ctrline{Tuesday, October 19, 1982}

\ppskip
{\bf Grading}:
5 possible points were assigned to each problem, except for problem 8,
which was assigned 15 points (10 for |partition| and 5 for |testpart|).

\pskip
{\bf Solutions}:
More than one solution is given for some of the problems; in
such cases the preferred answer is first.

\ppskip
\no(1)$|samelength|[u,v] ←$\par
$⊗⊗⊗⊗\IF\N u\OR\N v\THEN\N u\AND\N v$\par
$⊗⊗⊗⊗\ELSE |samelength|[\D u,\D v]$\par
\pskip
$⊗⊗⊗|samelength|[u,v] ←$\par
$⊗⊗⊗⊗\IF\N u\THEN\N v$\par
$⊗⊗⊗⊗\ELSE\IF\N v\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE |samelength|[\D u,\D v]$

\ppskip
\no(2)$|prup|[u,v]←$\par
$⊗⊗⊗⊗\IF\N u\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE (\A u\.\A v)\.|prup|[\D u,\D v]$\par
\pskip
In this problem (as well as in the others) it was OK to assume that the input
was reasonable, i.e.\ that $u$ and $v$ have the same length.  Some people
checked for cases where this did not hold and caused some default action, for
example
$$|prup|[\quote{(A B C)},\quote{(1 2)}]=\quote{((A . 1) (B . 2) C)}.$$
Another possibility is to terminate when $\N u\OR\N v$.  Terminating on
$\N u\AND\N v$ is inappropriate---if you are assuming that
the lists are the same length then $\N u$ is sufficient, but if
the lists are of different length then you
may end up taking the |cdr| of \NIL.

\ppskip
\no(3)$|istail|[u,v]←(u=v)\OR(\NOT\N v)\AND|istail|[u,\D v]$\par
\pskip
$⊗⊗⊗|istail|[u,v]←$\par
$⊗⊗⊗⊗\IF u=v\THEN\T$\par
$⊗⊗⊗⊗\ELSE\IF\N v\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE|istail|[u,\D v]$\par
\pskip
A common mistake here was to test $\N v$ before $u=v$.  The test for
$u=v$ must come first, since we want $|istail|[\NIL,\NIL]$ to be \T.
Incidentally, the external notation $u=v$ is an abbreviation for
$|equal|[u,v]$, or \quote{(EQUAL U V)} in internal form; and $u\EQ v$
is the external-form abbreviation for $|eq|[u,v]$, which is
\quote{(EQ U V)} internally.

\ppskip
\no(4)$|commontail|[u,v]←$\par
$⊗⊗⊗⊗\IF|istail|[u,v]\THEN u$\par
$⊗⊗⊗⊗\ELSE|commontail|[\D u,v]$\par
\pskip
The above definition is nice and simple, and it works!  Some people
started with the test $\IF\N u\THEN\NIL$, which is not needed since
|istail|, if correctly written, handles this case.  Most other solutions
involved |reverse|.  The one on page 161 of the book is the best of those
(though you weren't supposed to have read that far);
there were also some who tried to use |reverse| with no auxiliary functions,
resulting in a very messy, as well as inefficient, function.

\ppskip
\no(5)$|upto|[u,v]←$\par
$⊗⊗⊗⊗\IF u=v\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE\A v\.|upto|[u,\D v]$\par

\ppskip
\no(6)$|mapapp|[f,u]←$\par
$⊗⊗⊗⊗\IF\N u\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE f[\A u]*|mapapp|[f,\D u]$\par
\pskip
When you implement this in MacLisp, if you try to say \quote{(F (CAR U))}
for $f[\A u]$, you may get an error message.  There are three ways out of
this:\quad (1) say \quote{(FUNCALL F (CAR U))},\quad (2) say
\quote{(APPLY F (LIST (CAR U)))},\quad or (3) incant \quote{(SSTATUS PUNT NIL)}
to MacLisp and then you will be able to say \quote{(F (CAR U))}.  The
third option makes MacLisp actually do what it says on page 1-17 of the
manual, namely, when there is no function definition for \quote{F}, it
evaluates it.  Method (1) is preferable, though, since it is closer to
what may be found in other dialects of LISP.

\ppskip
\no(7)$|mapchoose|[p,u]←$\par
$⊗⊗⊗⊗\IF\N u\THEN\NIL$\par
$⊗⊗⊗⊗\ELSE\IF p[\A u]\THEN\A u\.|mapchoose|[p,\D u]$\par
$⊗⊗⊗⊗\ELSE |mapchoose|[p,\D u]$\par

\ppskip
\no(8)$|partition|[u,n]←$\par
$⊗⊗⊗⊗\IF n>|length|\,u\THEN\quote{ERROR}$\par
$⊗⊗⊗⊗\ELSE\IF n=|length|\,u\THEN\list{|mapcar|[|list|,u]}$\par
$⊗⊗⊗⊗\ELSE\IF n=1\THEN\list{\list{u}}$\par
$⊗⊗⊗⊗\ELSE |mapcar|[λv.\,(\list{\A u}\.v),|partition|[\D u,n-1]]$\par
$⊗⊗⊗⊗⊗⊗ *|mapcar|[λv.\,((\A u\.\A v)\.\D v),|partition|[\D u,n]]$\par
\pskip
Nobody in the class gave the above solution exactly, but it's the most
elegant one I've seen.  Some people had essentially the same idea, but
used named functions instead of the $λ$-expressions.
The idea behind this solution is that a partition of $u$ into $n$ sublists
(the book should have said non-null sublists) either has $\list{\A u}$ as the
first sublist, in which case the remainder is a partition of $\D u$ into
$n-1$ sublists, or it has a first sublist with more than one member; in
that case removing $\A u$ from the first sublist creates one of the
partitions of $\D u$ into $n$ sublists, so we can reverse the process by
``splicing'' $\A u$ into each member of $|partition|[\D u,n]$.
Several people did not include the proper level of lists in the base
cases of the recursion; this is important to make the function work
correctly.

\pskip
Another approach was to take initial segments of $u$ one at a time, and
add them to each member of the rest of $u$, partitioned into $n-1$
sublists, with appropriate termination cases.

\pskip
When you detect an error case, it is not necessary to do anything fancy.
In this case, returning the atom \quote{ERROR} is quite reasonable, since
we never expect the output of the function to be an atom.  In fact,
there might be a version of |partition| which calls itself recursively and
expects to get \quote{ERROR} back in some cases.

\pskip
$⊗⊗⊗|testpart|[p,u]←\N p\OR u=|appendlist|[\A p]\AND|testpart|[\D p,u]$\par
\vskip 2pt
$⊗⊗⊗|appendlist|[v]←\IF\N v\THEN\NIL\ELSE \A v*|appendlist|[\D v]$\par

\ppskip
\no(9)$|mirror|\,x←$\par
$⊗⊗⊗⊗\IF\AT x\THEN x$\par
$⊗⊗⊗⊗\ELSE (|mirror|\,\D x)\.(|mirror|\,\A x)$\par

\ppskip
\no(10)$|occur|[x,y]←$\par
$⊗⊗⊗⊗\IF\AT y\THEN x=y$\par
$⊗⊗⊗⊗\ELSE |occur|[x,\A y]\OR |occur|[x,\D y]$\par
\pskip
It isn't necessary to write $\IF\AT y\THEN(\IF x=y\THEN\T\ELSE\NIL)$, since
this is equivalent to the above.

\ppskip
\no(11)$|multiplicity|[x,y]←$\par
$⊗⊗⊗⊗\IF\AT y\THEN(\IF x=y\THEN 1\ELSE 0)$\par
$⊗⊗⊗⊗\ELSE|multiplicity|[x,\A y]+|multiplicity|[x,\D y]$\par

\ppskip
\no(12)$|ispath|[p,x]←$\par
$⊗⊗⊗⊗\N p\OR\NOT\AT x\AND$\par
$⊗⊗⊗⊗⊗⊗(\IF\A p=\quote{A}\THEN|ispath|[\D p,\A x])$\par
$⊗⊗⊗⊗⊗⊗(\ELSE|ispath|[\D p,\D x])$\par
\pskip
We could use |eq| instead of |equal| to save a few microseconds of computer
time.  The function above does no error checking; it assumes that $p$
is a list containing only \quote{A}'s and \quote{D}'s.

\ppskip
\no(13)$|depth|\,x←$\par
$⊗⊗⊗⊗\IF\AT x\THEN 0$\par
$⊗⊗⊗⊗\ELSE 1+|max|[|depth|\,\A x,|depth|\,\D x]$\par
\pskip
Most versions of LISP have |max| as a built-in function, but if you
didn't know that, you could include the definition
\pskip
$⊗⊗⊗|max|[m,n]←\IF m>n\THEN m\ELSE n$

\vfill\end